#pragma once
#include <vector>

template <class T>
class UnionFindSet
{
public
	UnionFindSet(int size)
		:_set(size, -1)
	{}

	size_t FindRoot(int x)
	{
		while (_ufs[x] >= 0)
		{
			x = _set[x];
		}
		return x;
	}

	void Union(int x, int y)
	{
		size_t root1 = FindRoot(x);
		size_t root2 = FindRoot(y);
		if (root1 != root2)
		{
			_set[root1] += _set[root2];
			_set[root2] = root1;
		}
	}

	size_t SetCount()
	{
		int count = 0;
		for (size_t i = 0; i < _set.size(); i++)
		{
			if (_set[i] < 0)
				count++;
		}
		return count;
	}
private:
	std::vector<T> _set;
};
